/**
 * 将所有叶子节点连接成链
 * 叶子节点的右指针用来指向下一个叶子
 */

#include"LinkedList.h"
#include"BiTree.h"

BiTree*head,*pre=nullptr;
/**
 * 中序遍历和先序遍历的叶子节点的访问顺序都是从左到右的
 * 这里选择中序遍历
 * 
 * 思想：设置前驱节点pre，初始为空，第一个叶子节点由head指向
 * 遍历到叶子节点的时候，就将他的前驱right指向他，
 * 最后一个叶子节点的right为空
 */
BiTree* makeChain(BiTree *bt){
    if(bt){//当前节点不为空的时候，递归进行
        makeChain(bt->left);//先左
        //然后自己，如果自己是叶子节点
        if(bt->left==nullptr&&bt->right==nullptr){
            //如果前驱为空，那么自己就是链表的head，同时将前驱指向自己
            if(pre==nullptr){
            head=bt;//这里显然不能这样赋值，但是有这么个意思就行
            pre=bt;
            //如果前驱不为空，那么正常链接
            }else{
                pre->right=bt;
                pre=bt;
            }
        }
        //最后再右
        makeChain(bt->right);
        //右递归结束后，pre指向的是最后一个节点，他的right是null
        pre->right=nullptr;
    }

    return head;
}
//时间复杂度O(n) 空间复杂度：两个辅助空间+n的栈空间O(n)
